package TwoPointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.OptionalInt;

/**
 * @Author: Darven
 * @CreateTime: 2025-03-31  17:00
 * @Description: TODO
 */
public class P42 {
    public static void main(String[] args) {
        P42Demo p42Demo = new P42Demo();
        int[] num={0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(p42Demo.trap1(num));;
    }
}

class P42Demo{
    public int trap(int[] height) {

        int ans=0;
        List<Integer> left=null;
        List<Integer> right=null;
        int maxIndex=0;
        for(int i=0;i<height.length;i++){
            if(height[i]>height[maxIndex]){
                maxIndex=i;
            }
        }
        int lMid=maxIndex;
        int rMid=maxIndex;
        int l=maxIndex-1;
        int r=maxIndex+1;
        //先进行左边相加
        while (l>0){
            left=new ArrayList<>();
           for(int i=l;i>=0;i--){
               if(height[l]<height[i]){
                   l=i;
               }
           }
           for(int i=l+1;i<lMid;i++){
               left.add(height[i]);
           }
            int count=0;
           for(int i:left){
               count+=i;
           }
            int sum=Math.min(height[l],height[lMid])*(lMid-l-1)-(int)count;
            ans+=sum;

            lMid=l;
            l=lMid-1;
        }

        while (r<height.length){
            right=new ArrayList<>();
            for(int i=r;i<height.length;i++){
                if(height[r]<height[i]){
                    r=i;
                }
            }
            for(int i=rMid+1;i<r;i++){
                right.add(height[i]);
            }
            int count=0;
            for(int i:right){
                count+=i;
            }
            int sum=Math.min(height[r],height[rMid])*(r-rMid-1)-(int)count;
            ans+=sum;

            rMid=r;
            r=rMid+1;
        }

        return ans;
    }

    public int trap1(int[] height) {
        /**
         * 哪边低，减哪边
         * */
        int ans=0;
        int length=height.length;

        int lMax=0,rMax=0;
        int l=0;
        int r=length-1;
        while (l<r){
            lMax=Math.max(lMax, height[l]);
            rMax=Math.max(rMax, height[r]);

            if(height[l]<height[r]){
                ans+=lMax-height[l];
                l++;
            }else{
                ans+=rMax-height[r];
                r--;
            }

        }
        return ans;
    }
}


